/*
 * @lc app=leetcode.cn id=406 lang=java
 *
 * [406] 根据身高重建队列
 */

// @lc code=start

import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]> () {
            @Override
            public int compare(int[] person1, int[] person2) {
                if(person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });

        List<int[]> res = new LinkedList<>();
        for(int i = 0; i < people.length; i++) {
            if(res.size() > people[i][1]) {
                res.add(people[i][1], people[i]);
            } else {
                res.add(res.size(), people[i]);
            }
        }
        return res.toArray(new int[res.size()][2]);
    }
}
// @lc code=end

